package com.mlh.stack;

import com.mlh.dp.编辑距离.两个字符串的删除操作;

import java.util.*;

/**
 * @author 缪林辉
 * @date 2024/6/19 16:05
 * @DESCRIPTION
 */
//nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
// 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
// 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，
// 并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
// 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
public class 下一个更大元素1 {

    public static void main(String[] args) {
        int[] nums1={4,1,2};
        int[] nums2={1,3,4,2};
        int[] res = method1(nums1, nums2);
        Arrays.toString(res);
    }

    public static int[] method1(int[] nums1, int[] nums2) {
        int[]res=new int[nums1.length];
        //利用每日温度的方法，先求出nums2中每个数的下一个更大元素存入到hash表中，
        // 然后根据nums1有的数字去hash表中找答案即可
        Deque<Integer> stack=new LinkedList<>();
        Map<Integer,Integer>map=new HashMap<>();
        stack.push(nums2[0]);
        for (int i = 1; i <nums2.length ; i++) {
            while (!stack.isEmpty()&&stack.peek()<nums2[i]){
                map.put(stack.peek(),nums2[i]);
                stack.pop();
            }
            stack.push(nums2[i]);
        }
        for (int i = 0; i < nums1.length; i++) {
            if (map.get(nums1[i])!=null){
                res[i]=map.get(nums1[i]);
            }else{
                res[i]=-1;
            }
        }
        return res;
    }
}
